/*
 * @Author: w
 * @Date: 2022-02-19 22:38:35
 * @Description: 剑指 Offer 24. 反转链表
 */

// 链表的基本使用 循环、递归

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */

// 循环
var reverseList = function (head) {
  let prev = null;
  let curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
};

// 栈
var reverseList = function (head) {
  if (head == undefined) return head;
  const stack = [];

  while (head) {
    stack.push(head);
    head = head.next;
  }
  const head1 = stack.pop();
  let ponit = head1;

  while (stack.length) {
    const node = stack.pop();
    node.next = null;
    ponit.next = node;
    ponit = ponit.next;
  }
  return head1;
};

// 递归
var reverseList = function (head) {
  let tail = head;
  const deep = function (cur, next) {
    if (next) {
      deep(next, next.next);
      next.next = cur;
    } else {
      tail = cur;
    }
  };
  if (head) {
    deep(head, head.next);
    head.next = null;
  }
  return tail;
};

// 递归
var reverseList = function (head) {
  if (head == null || head.next == null) {
    return head;
  }
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
};
